package dp;

import java.util.*;

/**
 * Description:
 * Author:    Dane
 * CreateTime:2024/10/14-下午3:15
 * Since  :   1.0
 * Version:   1.0
 */

//12345678910
//   aabaac
public class suanfa01 {

    public static int combinationSum4(int[] nums, int target) {
        int[] dp = new int[target + 1];
        //dp[j]=dp[j]+dp[j-nums[i]]
        dp[0] = 1;
        for (int i = 0; i <= target; i++) {
            for (int j = 0; j < nums.length; j++) {
                if (i >= nums[j]) {
                    dp[i] += dp[i - nums[j]];
                }
            }
            System.out.println(Arrays.toString(dp));
        }

        return dp[target];
    }

    public static int coinChange(int[] coins, int amount) {
        if (coins.length == 1) {
            if (coins[0] < amount) {
                int a = amount % coins[0];
                if (a == 0) {
                    return amount / coins[0];
                }
                return -1;

            } else if (coins[0] > amount) {
                return 0;
            } else {
                return 1;
            }
        }

        int[] dp = new int[amount + 1];
        dp[0] = 0;
        for (int i = 1; i < dp.length; i++) {
            dp[i] = Integer.MAX_VALUE;
        }

//        for (int i = 0; i < coins.length; i++) {
//            for (int j = coins[i]; j <= amount; j++) {
//                dp[j] = Math.min(dp[j], dp[j - coins[i]] + 1);
//
//            }
//            System.out.println(Arrays.toString(dp));
//
//        }

        for (int i = 0; i < coins.length; i++) {
            for (int j = coins[i]; j <amount; j++) {
                    dp[j]=Math.min(dp[j],dp[j-coins[i]]+1);
            }
        }
        return dp[amount];
    }

    public static int rob(int[] nums) {
        if (nums.length == 1) {
            return nums[0];
        }
        int[] dp = new int[nums.length];
//        dp[i]=max(nums[i]+dp[i-2],dp[i-1]);
        dp[0] = nums[0];
        dp[1] = Math.max(nums[0], nums[1]);
        for (int i = 2; i < nums.length; i++) {
            dp[i] = Math.max(nums[i] + dp[i - 2], dp[i - 1]);
            System.out.println(Arrays.toString(dp));
        }

        return dp[nums.length - 1];
  
    }


    public static void main(String[] args) {
//        int coins[] = {1};
//        int amount = 2;
//        System.out.println(coinChange(coins, amount));
//       int nums[] = {1,2,3};
//       int target = 4;
//        System.out.println(combinationSum4(nums,target));

        int nums[] = {1, 2, 3, 1, 5};
        System.out.println(rob(nums));
    }
}
